
//1277.统计全为1的正方形子矩阵
class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();

        auto r_max=[&](int level)
        {
            vector<int> nums(n);  //统计从level层开始向下连续1的长度
            for(int i=0;i<n;i++)
            {
                int j=level;
                while(j<m&&matrix[j][i]==1) j++;
                nums[i]=j-level;
            }
            //使用一个栈记录前面的位置的高度
            int each=0;
            for(int i=0;i<n;i++)
            {
                if(nums[i]) each++;
                int l=nums[i];
                for(int j=i-1;j>=0;j--)
                {
                    l=min(l,nums[j]);
                    if(l>=i-j+1) each++;
                    else break;
                }        
            }
            return each;
        };

        int ret=0;
        for(int k=0;k<m;k++)  //对每一层都进行统计
            ret+=r_max(k);
        
        return ret;
    }
};